1. Field of the Invention:
This invention relates generally to memory circuits and, more particularly, to special-purpose memory circuits used in digital signal processing. There is a general class of computational search problems in which numerical data must be sorted or classified in accordance with its relationship to one or more sets of dimensional limits. It is with this class of problems that the present invention is concerned.
For example, in the processing of census data it may be useful to determine the number of people within specified age limits living within a specified geographical area, defined by a numerical range of ZIP codes. Clearly, such a problem is easily handled by a programmable general-purpose digital computer. In some cases, the speed of operation of the computer is of no concern, since there is typically no need for an immediate solution to the problem. However, there are some problems in the same general class that must be solved more rapidly. In some cases, the solution is required in "real time," or almost instantly as a data stream is received and processed. A programmed digital computer may still be fast enough to satisfy the requirements of some of these applications. For others, however, even the fastest programmable computers cannot provide real-time solutions to the complex signal processing problems that are involved.
One area in which real-time solutions are typically required is the field of pattern recognition and image processing. For example, the processing of photographic data from an earth-orbiting satellite may require that areas having a particular color and a particular shape be identified and counted. Another form of pattern recognition is the identification of the source of a spoken word by its spectral content, or the identification of a signal source by its spectral content. Pattern recognition has many other well known applications in both military and commercial areas.
Another important example of the type of signal processing with which the invention is concerned is the processing of radar pulses. The analysis of radar pulses from multiple sources is frequently too complex for human operators to be able to handle rapidly and reliably. In a typical system, each received radar signal is preprocessed into digital fields that characterize and completely define the signal. The fields might contain such information as time of arrival, frequency, pulse amplitude, pulse width, angle of arrival, and so forth. In a typical application, there may be many such signals whose sources are known and are of no consequence to the signal processing. Since the characteristics of these signals from known sources are also known, a first processing step is usually to filter out these known signals from ones of more particular interest. This filtering step is analogous to finding the number of people in a selected age group in particular region of the country, but in the radar example the specified items are discarded as uninteresting rather than further analyzed. Both applications, however, are examples of a process that might be described as environmental filtering.
The cross-referenced application, which is not believed to be prior art with respect to the invention claimed in this application, discloses a window-addressable memory in which input words having multiple data fields can be compared with up to eight sets of upper and lower "window" limits for the data fields, and match indicators are generated if all data fields in the input word fall within the upper and lower window limits stored in the circuit. The input words may be thought of as vectors in an n-dimensional space, where n is the number of data fields in the input word. The window-addressable memory (WAM) circuit permits the comparison of an input vector with up to eight sets of dimensional limits. If an application requires a comparison with a greater number of windows, multiple WAMs can be cascaded, but there is a practical limit imposed by the relatively high cost of the WAM circuits.
2. Prior Art:
One approach taken in the prior art has been to provide more comparison registers, containing upper and lower bounds, on a single processing chip. For example, in a paper by Craig A. Hanna entitled "The Associative Comparator: Adds New Capabilities to ESM Signal Processing," Defense Electronics, February, 1984, pp. 51-62, the author describes a comparison chip with thirty-two comparison registers, and suggests a future design with 512 comparison registers. Such designs are, of course, complex and correspondingly costly to implement. Moreover, even with the availability of circuits with hundreds of comparison registers, or windows, there are still some applications that require comparisons between an input data vector and a very large number of windows.
Hashing techniques have been employed to reduce the processing requirements for searching. This is basically a software solution in which data fields are transformed into a different arrangement, which is more compact and easier to manipulate. Hashing, or hash coding, has been usefully employed in one- and two-dimensional searches. However, the complexity and routing of hashing approaches becomes questionable as the number of dimensions increases, making file updating unmanageable for real-time implementation. Also, if the data to be searched through is rapidly changing in either content or amount, hashing is difficult to apply. More importantly, implementation of windowed or "fuzzy" comparisons are difficult if hashing techniques are used. Examples of hashing techniques may be found in D. E. Knuth, "The Art of Computer Programming," Vol. 3: Sorting and Searching, Addison Wesley, Reading, Mass., 1973, and in C. J. Date, "An Introduction to Database Systems," Addison Wesley, Reading, Mass., 2nd Ed., 1977.
Fully parallel content addressable memories compare the full width of a relatively large number of object data words, stored in a memory, in parallel against a search vector. This results in extremely fast searches and flexibility to handle complex searches. However, fully parallel content addressable memories are complex and relatively costly. Holographic memories are of this type, and are complex and difficult to update. See, for example, T. Kohonen, "Content-Addressable Memories," Springer-Verlag, New York, N.Y., 1980.
Bit-serial or byte serial memory circuits make comparisons with object data words stored in a memory by accessing multiple words in parallel, but only one bit or byte at a time for the multiple words accessed. This was the approach adopted for the Goodyear STARAN processors described in the following four papers:
K. E. Batcher, "Bit Serial Parallel Processing Systems," IEEE Trans. Computers, Vol. C-31, pp. 377-84, May, 1982;
K. E. Batcher, "The Multidimensional Access Memory in STARAN," IEEE Trans. Computers, Vol. C-26, pp. 174-77, February, 1977;
K. E. Batcher, "STRAN Series E," 1977 Int'l Conf. Parallel Processing, pp. 144-53, August, 1977; and
E. W. Davis, "STARAN Parallel Processor System Software," Proc. of 1974 Nat. Comp. Conf., AFIPS Conf. Proc., Vol. 43, p. 17.
The bit-serial or byte-serial mechanism potentially supports very long data words, with some flexibility in format. The hardware for windowing operations is relatively complex, and the memory architecture requires accessing both in parallel, for up to a limited number of words, and serially, for a larger number of words. Also, direct addressing of the memory is difficult, as is incorporating such a circuit into a practical system.
Finally, bit-parallel content addressable memories perform an association over an entire object data word at a time, with fully parallel hardware comparisons over the entire word. With the exception of the system described in the Hanna paper discussed above, prior circuits of this type did not support n-dimensional vectors and did not have the ability to perform fuzzy comparisons.
It will be appreciated from the foregoing that there is still a need for improvement in the field of window-addressable or "fuzzy" associative memories. In particular, what is needed is a memory system of this type that is simple and convenient to use, and is capable of handling many more windows than can presently be handled, but without excessive complexity or cost. The present invention is directed to this end.